package dynamic;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        // dp[i][j] 表示以字符串s1的第i个字符结尾的与以s2的第j个字符串结尾的最长子串长度
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        // 状态转移方程：
        // if (s1.charAt(i) == s2.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1
        // else dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])
        int index = 0;
        for (int i = 0; i < s1.length(); i ++) {
            for (int j = 0; j < s2.length(); j ++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        //从动态规划数组末尾开始
        int i = s1.length(), j = s2.length();
        Stack<Character> s = new Stack<Character>();
        while (dp[i][j] != 0) {
            //来自于左方向
            if (dp[i][j] == dp[i - 1][j]) {
                i--;
            }
            //来自于上方向
            else if (dp[i][j] == dp[i][j - 1]) {
                j--;
            }
            //来自于左上方向
            else if (dp[i][j] > dp[i - 1][j - 1]) {
                i--;
                j--;
                //只有左上方向才是字符相等的情况，入栈，逆序使用
                s.push(s1.charAt(i));
            }
        }
        String res = "";
        //拼接子序列
        while (!s.isEmpty()) {
            res += s.pop();
        }
        //如果两个完全不同，返回字符串为空，则要改成-1
        return !res.isEmpty() ? res : "-1";
    }
}